/*
 *  linux/kernel/blk_dev/ll_rw.c
 *
 * (C) 1991 Linus Torvalds
 */

/*
 * This handles all read/write requests to block devices
 */
#include <errno.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/system.h>

#include "blk.h"

/*
 * The request-struct contains all necessary data
 * to load a nr of sectors into memory
 */
struct request request[NR_REQUEST];  /* 请求项数组 */

/*
 * used to wait on when there are no free requests
 是用于在请求数组没有空闲项时进程的临时等待处。
 */
struct task_struct * wait_for_request = NULL;  /* 请求项数组的等待队列（数组满员时等待） */

/* blk_dev_struct is:
 *	do_request-address
 *	next-request
 */
/* 块设备表（数组），每种块设备占用一项。*/
struct blk_dev_struct blk_dev[NR_BLK_DEV] = {
	{ NULL, NULL },		/* no_dev */
	{ NULL, NULL },		/* dev mem */
	{ NULL, NULL },		/* dev fd */
	{ NULL, NULL },		/* dev hd */
	{ NULL, NULL },		/* dev ttyx */
	{ NULL, NULL },		/* dev tty */
	{ NULL, NULL }		/* dev lp */
};

// 锁定指定缓冲块。
// 如果指定的缓冲块已经被其他任务锁定，则使自己睡眠（不可中断地等待），直到被执行解锁缓冲块的任务明确地唤醒。
static inline void lock_buffer(struct buffer_head * bh)
{
	cli();
	while (bh->b_lock)
		sleep_on(&bh->b_wait);
	bh->b_lock=1;
	sti();
}

// 释放（解锁）锁定的缓冲区。
static inline void unlock_buffer(struct buffer_head * bh)
{
	if (!bh->b_lock)
		printk("ll_rw_block.c: buffer not locked\n\r");
	bh->b_lock = 0;   /* 清锁定标志 */
	wake_up(&bh->b_wait);  // 唤醒等待该缓冲区的任务
}

/*
 * add-request adds a request to the linked list.
 * It disables interrupts so that it can muck with the
 * request-lists in peace.
 */

// 向链表中加入请求项
// 参数 dev 是指定块设备结构指针，该结构中有处理请求项函数指针和当前正在请求项指针；
// 参数 req 是已设置好内容的请求项结构指针。
// 实现：本函数把已经设置好的请求项 req 添加到指定设备的请求项链表中。
// 		1、如果该设备的当前请求请求项指针为空，则可以设置 req 为当前请求项并立刻调用设备请求项处理函数。
// 		2、否则就把 req 请求项插入到该请求项链表中。
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
	struct request * tmp;

	req->next = NULL;
	cli();
	if (req->bh)
		req->bh->b_dirt = 0;
	// 查看指定设备是否有当前请求项，即查看设备是否正忙。如果指定设备 dev 当前请求项 (current_request）子段为空，则表示目前该设备没有请求项，本次是第1个请求项，也是唯一的一个。因此可将块设备当前请求指针直接指向该请求项，并立刻执行相应设备的请求函数。
	if (!(tmp = dev->current_request)) {
		dev->current_request = req;
		sti();
		(dev->request_fn)();
		return;
	}
	// 通过电梯算法，将req请求项插入到请求项链表中
	// tmp为请求链表中的节点
	for ( ; tmp->next ; tmp=tmp->next)
		// 电梯算法实现：（除第一项外，后面的请求项是一个递增(或递减)的序列：https://zhuanlan.zhihu.com/p/608284595）
		// 先考虑两种插入req的极端场景：
		// 1、如果req是当前队列中的最低优先级，此时会插入到最后；
		// 2、如果req是当前队列中的最高优先级，此时会插入到当前请求之后，成为第2个节点。所以该算法可能出现当前节点（第1个节点）优先级低于第2个节点。但是IN_ORDER(req,tmp->next)保证了从第2个节点开始及其后续所有节点都是优先级递减的
		// 基于上面的描述，所以会出现如下两种情况：
		// 符合情况1：  优先级：当前节点 > req > next节点
		// 符合情况2： "req >= 当前节点"  &&  "next节点 >= 当前节点" && "req >  next节点"  。有一个场景：当前正在处理请求（比如write1），此时插入一个请求比当前优先级高（比如read1）。然后当前请求仍没处理完，又插入一个请求更高的请求（比如read2 > read1）。
		// next节点 >= 当前节点 ：出现
		if ((IN_ORDER(tmp,req) || 
		    !IN_ORDER(tmp,tmp->next)) &&
		    IN_ORDER(req,tmp->next))
			break;
	// 将req插入到tmp和tmp->next之间（正是因为req不是插入到最首部，而是插入第2个节点处，所以导致从第2个节点开始才是优先级递减的，第1个优先级可能不是最高的）
	req->next=tmp->next;
	tmp->next=req;
	sti();
}

// 为块设备创建块设备读写请求项，并插入到指定块设备请求队列中
// 参数：
// major 是主设备号；
// rw 是指定命令；
// bh 是存放数据的缓冲区头指针。
static void make_request(int major,int rw, struct buffer_head * bh)
{
	struct request * req;
	int rw_ahead;

/* WRITEA/READA is special case - it is not really needed, so if the */
/* buffer is locked, we just forget about it, else it's a normal read */
	// 该函数首先对命令 READA/WRITEA 的情况进行一些处理。
	// 对于这两个命令，当指定的缓冲区正在使用而己被上锁时，就放弃预读/写请求。否则就作为普通的 READ/WRITE 命令进行操作。
	if ((rw_ahead = (rw == READA || rw == WRITEA))) {  /* 设置是否预读/写命令了标志 rw_ahead */
		if (bh->b_lock)
			return;
		if (rw == READA)
			rw = READ;
		else
			rw = WRITE;
	}
	if (rw!=READ && rw!=WRITE)
		panic("Bad block dev command, must be R/W/RA/WA");

	/*
	对命令 rw 进行了一番处理之后，现在只有 READ 或 WRITE 两种命令。
	在开始生成和添加相应读/写数据请求项之前，我们再来看看此次是否有必要添加请求项。
	在两种情况下可以不必添加请求项:
	一是当命令是写（WRITE），但缓冲区中的数据在读入之后并没有被修改过；
	二是当命令是读（READ），但缓冲区中的数据己经是更新过的，即与块设备上的完全一样。
	
	因此这里首先锁定缓冲区对其检查一下。如果此时缓冲区己被(其他进程)上锁，则当前任务就会睡眠，直到被明确地唤醒。
	再次唤醒后，检查如果确实是属于上述两种情况，那么就可以直接解锁缓冲区，并返回。

	这几行代码体现了高速缓冲区的用意，在数据可靠的情况下就无须再执行硬盘操作，而直接使用内存中的现有数据。
	*/
	lock_buffer(bh); /* 如果bh已经被上锁，就会将当前任务睡眠。再次唤醒后，再上锁 */
	if ((rw == WRITE && !bh->b_dirt) || (rw == READ && bh->b_uptodate)) {
		unlock_buffer(bh);  /* 放弃此次请求操作 */
		return;
	}
	// 生成并添加读/写请求项
repeat:
/* we don't allow the write-requests to fill up the queue completely:
 * we want some room for reads: they take precedence. The last third
 * of the requests are only for reads.
 * 我们不能让队列中全都是写请求项：我们需要为读请求保留一些空间：
 * 读操作是优先的。请求队列的后三分之一空间仅用于读请求项。（数组搜索过程从请求数组末端开始）
 */

	/*
	添加读/写请求项逻辑：
	首先我们需要在请求数组中寻找到一个空闲项（槽）来存放新请求项。搜索过程从请求数组末端开始。
	根据上述要求，对于读命令请求，我们直接从队列末尾开始搜索，而对于写请求就只能从队列 2/3处向队列头处搜索空项填入。
	于是我们开始从后向前搜索，当请求结构 request 的设备字段 dev 值=-1时， 表示该项未被占用（空闲）。
	如果没有一项是空闲的（此时请求项数组指针已经搜索越过头部），则查看此次请求是否是提前读/写（READA 或 WRITEA)，如果是则放弃此次请求操作。
	否则让本次请求操作先睡眠（以等待请求队列腾出空项)，过一会再来搜索请求队列。
	*/
	if (rw == READ)
		req = request+NR_REQUEST;
	else
		req = request+((NR_REQUEST*2)/3);
/* find an empty request */
	while (--req >= request)
		if (req->dev<0)
			break;
/* if none found, sleep on new requests: check for rw_ahead */
	if (req < request) {
		// 如果是预读写
		if (rw_ahead) {
			unlock_buffer(bh); /* 放弃此次请求操作 */
			return;
		}
		// 如果不是预读写
		sleep_on(&wait_for_request);
		// 被明确唤醒时，重新生成请求项
		goto repeat;
	}
/* fill up the request-info, and add it to the queue */
	// 找到一个空项项，此处将请求项填充成员变量
	req->dev = bh->b_dev;
	req->cmd = rw;
	req->errors=0;
	req->sector = bh->b_blocknr<<1;  /* 起始扇区。块号转换成扇区号(1块=1k=2扇区)。 */
	req->nr_sectors = 2;
	req->buffer = bh->b_data;
	req->waiting = NULL;
	req->bh = bh;
	req->next = NULL;
	// 插入到指定块设备请求队列中
	add_request(major+blk_dev,req);
}

// 低层读写数据块函数（生成写设备块请求项）
// 实现对 make_request 的封装
void ll_rw_block(int rw, struct buffer_head * bh)
{
	unsigned int major;

	if ((major=MAJOR(bh->b_dev)) >= NR_BLK_DEV ||
	!(blk_dev[major].request_fn)) {
		printk("Trying to read nonexistent block-device\n\r");
		return;
	}
	make_request(major,rw,bh);
}

// 块设备初始化函数，由初始化程序 main.c 调用(init/main.c,128）。
// 初始化请求数组，将所有请求项置为空闲项(dev = -1)。有32项(NR_REQUEST = 32）。
void blk_dev_init(void)
{
	int i;

	for (i=0 ; i<NR_REQUEST ; i++) {
		request[i].dev = -1;
		request[i].next = NULL;
	}
}
